package strain.domain.interval_set_alt;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class IntervalSet<T extends Comparable<T>> implements Iterable<Interval<T>> {
    
    private SortedSet<Interval<T>> intervals;

    private static <T extends Comparable<T>> SortedSet<Interval<T>> combine(final Collection<Interval<T>> intervals, final int minIncludeCount, final int initialDepth){
        // minIncludeCount defines the number of intervals an element must be present in to be present in the result.
        // if minIncludeCount is 1, then an element is included in the result if it's present in at least 1 interval (union)
        // if minIncludeCount is inverals.size(), then an element is included in the result if it's present in all the intervals (intersection)
        List<IntervalBound<T>> bounds = new ArrayList<IntervalBound<T>>(intervals.size() * 5 * 2);
        for(Interval<T> i: intervals){
            bounds.add(i.getLow());
            bounds.add(i.getHigh());
        }
        Collections.sort(bounds);
        return combine(bounds, minIncludeCount, initialDepth);
    }
    
    private static <T extends Comparable<T>> List<IntervalBound<T>> normalize(final List<IntervalBound<T>> sortedBounds){
        // this method is private and assumes that the list of bounds passed in has been Collections.sort()ed already
        
        //TODO: this should be done with a stack!!!
        
        // this should remove sequences like {... a) [a ...} and {... a] (a ...}.  Their presence makes it look like there should be bounds there,
        // but the set is actually continuous right through them...
        List<IntervalBound<T>> sb = new LinkedList<IntervalBound<T>>(sortedBounds);
        ListIterator<IntervalBound<T>> it = sb.listIterator();
        if (it.hasNext()){
            IntervalBound<T> a = it.next();
            while(it.hasNext()){
                IntervalBound<T> b = it.next();
                if (a.getBound().equals(b.getBound()) && (a.isLower() != b.isLower()) && (a.isInclusive() != b.isInclusive())){
                    it.previous(); // returns b again (going backwards)
                    it.remove();
                    it.previous(); // returns a (going backwards)
                    it.remove();
                    if (it.hasPrevious()){
                        it.previous(); // returns bound before a (going backwards, next call to next() will return this bound again)
                    } // else we just got done removing the beginning of the list, nothing to go back to...
                    if (it.hasNext()){
                        a = it.next();
                    } // else we are at the end of the list, the while loop is about to exit.
                } else {
                    a = b;
                }
            }
        }
        return sb;
    }

    private static <T extends Comparable<T>> SortedSet<Interval<T>> combine(final List<IntervalBound<T>> sortedBounds, final int minIncludeCount, final int initialDepth){
        // this method is private and assumes that the list of bounds passed in has been Collections.sort()ed already

        ArrayList<IntervalBound<T>> sb = new ArrayList<IntervalBound<T>>(normalize(sortedBounds));
        
        // if bounds has come in with leading upper bounds, and/or trailing lower bounds, this must be some intermediate complement form
        // they cannot be part of result, so they need to be ignored.  The depth remains accurate because the top level is always depth
        // zero, if these strange bounds exist then they signify an initial or final depth > 0, rather than the normal 0 initial depth.

        // find first lower bound (should commonly be the zeroth element)
//        int i = 0;
//        while((i < sb.size()) && sb.get(i).isUpper()) ++i;
        
        SortedSet<Interval<T>> result = new TreeSet<Interval<T>>(new Interval.LowerBoundComparator<T>());
        IntervalBound<T> low = null;
        int depth = initialDepth; // since we have iterated through any leading upper bounds, we are now at depth zero.

        for(int i = 0; i < sb.size(); ++i){
            IntervalBound<T> b = sb.get(i);
            if (b.isLower()){
                if (depth == minIncludeCount-1){
                    low = b;
                }
                ++depth;
            } else { // if (b.isUpper())
                --depth;
                if ((depth == minIncludeCount-1) && (low != null)){
                    result.add(new Interval<T>(low, b));
                    low = null;
                }
            }
        }
        return result;
    }
    
    public static <T extends Comparable<T>> IntervalSet<T> union(final Collection<IntervalSet<T>> sets){
        Collection<Interval<T>> intervals = new LinkedList<Interval<T>>();
        for(IntervalSet<T> s: sets){
            intervals.addAll(s.intervals);
        }
        return new IntervalSet<T>(combine(intervals, 1, 0));
    }
    
    public static <T extends Comparable<T>> IntervalSet<T> intersection(final Collection<IntervalSet<T>> sets){
        Collection<Interval<T>> intervals = new LinkedList<Interval<T>>();
        for(IntervalSet<T> s: sets){
            if (s.isEmpty()) return new IntervalSet<T>();
            intervals.addAll(s.intervals);
        }
        return new IntervalSet<T>(combine(intervals, sets.size(), 0));
    }
    
    private IntervalSet(final SortedSet<Interval<T>> intervals){
        // this constructor is private, and assumes that the intervals are in the right order, and don't overlap...
        this.intervals = intervals;
    }

    public IntervalSet(final IntervalSet<T> set){
        this(set.intervals);
    }
    
    public IntervalSet(final Interval<T> interval){
        this.intervals = new TreeSet<Interval<T>>(new Interval.LowerBoundComparator<T>());
        this.intervals.add(interval);
    }
    
    public IntervalSet(final T value){
        this(new Interval<T>(value, value));
    }
    
    public IntervalSet(){
        this.intervals = new TreeSet<Interval<T>>(new Interval.LowerBoundComparator<T>());
    }
    
    public int intervalCount(){
        return this.intervals.size();
    }
    
    public boolean isEmpty(){
        return this.intervals.isEmpty();
    }
    
    public boolean isEmptySet(){
        return this.intervals.isEmpty();
    }
    
    public IntervalBound<T> getLowerBound(){
        return this.intervals.first().getLow();
    }
    
    public IntervalBound<T> getUpperBound(){
        return this.intervals.last().getHigh();
    }
    
    public Iterator<Interval<T>> iterator(){
        return Collections.unmodifiableSortedSet(this.intervals).iterator();
    }
    
    public boolean supersetOf(final IntervalSet<T> set){
        return set.subsetOf(this);
    }
    
    public boolean subsetOf(final IntervalSet<T> set){
        return difference(set).isEmpty();
    }
    
    private ArrayList<IntervalBound<T>> complementBounds(){
        // the result of this method with automatically be sorted by virtue of it being iteratively constructed form an already sorted list
        ArrayList<IntervalBound<T>> result = new ArrayList<IntervalBound<T>>(this.intervals.size() * 2);
        for(Interval<T> i: this){
            result.add(i.getLow().complement());
            result.add(i.getHigh().complement());
        }
        return result;
    }
    
    public IntervalSet<T> intersection(final IntervalSet<T> set){
        if (isEmptySet()) return this;
        if (set.isEmptySet()) return set;
        
        List<IntervalSet<T>> sets = new ArrayList<IntervalSet<T>>(2);
        sets.add(this);
        sets.add(set);
        return IntervalSet.intersection(sets);
    }
    
    public IntervalSet<T> union(final IntervalSet<T> set){
        if (set.isEmptySet()) return this;
        if (isEmptySet()) return set;
        
        List<IntervalSet<T>> sets = new ArrayList<IntervalSet<T>>(2);
        sets.add(this);
        sets.add(set);
        return IntervalSet.union(sets);
    }
    
    public IntervalSet<T> difference(final IntervalSet<T> set){
        if (isEmptySet() || set.isEmptySet()) return this;
        
        ArrayList<IntervalBound<T>> result = set.complementBounds();
        for(Interval<T> i: this){
            result.add(i.getLow());
            result.add(i.getHigh());
        }
        Collections.sort(result);
        return new IntervalSet<T>(combine(result, 2, 1));
    }
    
    public IntervalSet<T> complement(final IntervalSet<T> universalSet){
        if (isEmptySet()) return universalSet;
        if (this.equals(universalSet)) return new IntervalSet<T>();

        return universalSet.difference(this);
    }
    
    public IntervalSet<T> symmetricDifference(final IntervalSet<T> set){
        if (set.isEmptySet()) return this;
        if (isEmptySet()) return set;
        
        return union(set).difference(intersection(set));
    }
    
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        
        Iterator<Interval<T>> i = this.intervals.iterator();
        if (i.hasNext()){
            Interval<T> interval = i.next();
            sb.append(interval);
        }
        while (i.hasNext()){
            Interval<T> interval = i.next();
            sb.append(" ").append(interval);
        }
        
        sb.append("}");
        return sb.toString();
    }
    
    @Override
    public int hashCode(){
        return this.intervals.hashCode();
    }
    
    @SuppressWarnings("unchecked")
    @Override
    public boolean equals(final Object o){
        if (this == o) return true;
        if ((o == null) || (!o.getClass().equals(this.getClass()))) return false;
        IntervalSet<T> is = (IntervalSet<T>) o;
        return this.intervals.equals(is.intervals);
    }
    
    public static <T extends Comparable<T>> String summarize(final IntervalSet<T> is){
        StringBuilder sb = new StringBuilder();
        sb.append(is).append("\n");
        sb.append("intervalCount()=").append(is.intervalCount()).append("\n");
        sb.append("isEmptySet()=").append(is.isEmptySet());//.append("\n");
        if (!is.isEmptySet()){
            sb.append("\n");
            sb.append("getLowerBound()=").append(is.getLowerBound()).append("\n");
            sb.append("getUpperBound()=").append(is.getUpperBound());//.append("\n");
        }
        return sb.toString();
    }
    
    public static <T extends Comparable<T>> String summarize(final IntervalSet<T> a, final IntervalSet<T> b){
        StringBuilder sb = new StringBuilder();
        sb.append("a:").append(a).append(" -- ").append("b:").append(b).append("\n");
        sb.append("a.supersetOf(b)=").append(a.supersetOf(b)).append("\n");
        sb.append("b.supersetOf(a)=").append(b.supersetOf(a)).append("\n");
        sb.append("a.subsetOf(b)=").append(a.subsetOf(b)).append("\n");
        sb.append("b.subsetOf(a)=").append(b.subsetOf(a)).append("\n");
        sb.append("a.intersection(b)=").append(a.intersection(b)).append("\n");
        sb.append("b.intersection(a)=").append(b.intersection(a)).append("\n");
        sb.append("a.union(b)=").append(a.union(b)).append("\n");
        sb.append("b.union(a)=").append(b.union(a)).append("\n");
        sb.append("a.difference(b)=").append(a.difference(b)).append("\n");
        sb.append("b.difference(a)=").append(b.difference(a)).append("\n");
        sb.append("a.symmetricDifference(b)=").append(a.symmetricDifference(b)).append("\n");
        sb.append("b.symmetricDifference(a)=").append(b.symmetricDifference(a)).append("\n");
        
        return sb.toString();
    }
    
    public static void main(final String[] args){
        System.out.println("Hello World!");
        
        IntervalSet<Double> universe = new Interval<Double>(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, false, false).asIntervalSet();
        
        Set<IntervalSet<Double>> iss = new HashSet<IntervalSet<Double>>();
        iss.add(universe);                                                      // {(-Infinity Infinity)}
        iss.add(new IntervalSet<Double>());                                     // {}
        iss.add(new IntervalSet<Double>(2.0));                                  // {[2.0 2.0]}
        iss.add(new Interval<Double>(1.0, 2.0).asIntervalSet());                // {[1.0 2.0]}
        iss.add(new Interval<Double>(1.0, 2.0, false).asIntervalSet());         // {(1.0 2.0)}
        iss.add(new Interval<Double>(1.0, 2.0, true, false).asIntervalSet());   // {[1.0 2.0)}
        iss.add(new Interval<Double>(2.0, 3.0, false, true).asIntervalSet());   // {(2.0 3.0]}
        iss.add(new Interval<Double>(2.0, 3.0).asIntervalSet());                // {[2.0 3.0]}

        int size = 0;
        while (size < iss.size()){
            size = iss.size();
            Set<IntervalSet<Double>> newis = new HashSet<IntervalSet<Double>>();
            for(IntervalSet<Double> is1: iss){
                newis.add(is1.complement(universe));
                for(IntervalSet<Double> is2: iss){
                    newis.add(is1.difference(is2));
                    newis.add(is1.intersection(is2));
                    newis.add(is1.symmetricDifference(is2));
                    newis.add(is1.union(is2));
                }
            }
            iss.addAll(newis);
        }
        
        int failures = 0;
        int tests = 0;
        for(IntervalSet<Double> a: iss){
            IntervalSet<Double> ac = a.complement(universe);
            IntervalSet<Double> acc = ac.complement(universe);
            IntervalSet<Double> aNa = a.intersection(a);
            IntervalSet<Double> aUa = a.union(a);
            IntervalSet<Double> aMa = a.difference(a);
            IntervalSet<Double> aXORa = a.symmetricDifference(a);
            if (!a.equals(acc)){ // a = a''
                System.out.println("WRONG... a: " + a + "; a'': " + acc);
                ++failures;
            }
            if (!a.equals(aNa)){ // a = aNa
                System.out.println("WRONG... a: " + a + "; aNa: " + aNa);
                ++failures;
            }
            if (!a.equals(aUa)){ // a = aUa
                System.out.println("WRONG... a: " + a + "; aUa: " + aUa);
                ++failures;
            }
            if (!aMa.isEmptySet()){
                System.out.println("WRONG... a: " + a + "; aMa: " + aMa);
                ++failures;
            }
            if (!aXORa.isEmptySet()){ // aXORa = {}
                System.out.println("WRONG... a: " + a + "; aXORa: " + aXORa);
                ++failures;
            }
            tests += 5;
            for(IntervalSet<Double> b: iss){
                IntervalSet<Double> bc = b.complement(universe);
                IntervalSet<Double> aNb = a.intersection(b);
                IntervalSet<Double> bNa = b.intersection(a);
                IntervalSet<Double> aUb = a.union(b);
                IntervalSet<Double> bUa = b.union(a);
                IntervalSet<Double> acUbc_c = ac.union(bc).complement(universe);
                IntervalSet<Double> acNbc_c = ac.intersection(bc).complement(universe);
                IntervalSet<Double> aXORb = a.symmetricDifference(b);
                IntervalSet<Double> bXORa = b.symmetricDifference(a);
                IntervalSet<Double> aMb = a.difference(b);
                IntervalSet<Double> aNbc = a.intersection(bc);
                IntervalSet<Double> bMa = b.difference(a);
                IntervalSet<Double> aMb_U_bMa = aMb.union(bMa);
                IntervalSet<Double> aUb_M_aNb = aUb.difference(aNb);
                if (!aNb.equals(bNa)){ // aNb = bNa
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aNb: " + aNb + "; bNa: " + bNa);
                    ++failures;
                }
                if (!aUb.equals(bUa)){ // aUb = bUa
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aUb: " + aUb + "; bUa: " + bUa);
                    ++failures;
                }
                if (!aNb.equals(acUbc_c)){ // aNb = (a'Ub')'
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aNb: " + aNb + "; (a'Ub')': " + acUbc_c);
                    ++failures;
                }
                if (!aUb.equals(acNbc_c)){ // aUb = (a'Nb')'
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aUb: " + aUb + "; (a'Nb')': " + acNbc_c);
                    ++failures;
                }
                if (!aXORb.equals(bXORa)){ // aXORb = bXORa
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aXORb: " + aXORb + "; bXORa: " + bXORa);
                    ++failures;
                }
                if (!aMb.equals(aNbc)){ // aMb = aNb'
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aMb: " + aMb + "; aNb': " + aNbc);
                    ++failures;
                }
                if (!aXORb.equals(aMb_U_bMa)){ // aXORb = (a-b)U(b-a)
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aXORb: " + aXORb + "; (a-b)U(b-a): " + aMb_U_bMa);
                    ++failures;
                }
                if (!aXORb.equals(aUb_M_aNb)){ // aXORb = (aUb)-aNb
                    System.out.println("WRONG... a: " + a + "; b: " + b + "; aXORb: " + aXORb + "; (aUb)-aNb: " + aUb_M_aNb);
                    ++failures;
                }
                tests += 8;
                for(IntervalSet<Double> c: iss){
                    IntervalSet<Double> aNc = a.intersection(c);
                    IntervalSet<Double> aUc = a.union(c);
                    IntervalSet<Double> bNc = b.intersection(c);
                    IntervalSet<Double> bUc = b.union(c);
                    IntervalSet<Double> aU_bNc = a.union(bNc);
                    IntervalSet<Double> aUb_N_aUc = aUb.intersection(aUc);
                    IntervalSet<Double> aN_bUc = a.intersection(bUc);
                    IntervalSet<Double> aNb_U_aNc = aNb.union(aNc);
                    if (!aU_bNc.equals(aUb_N_aUc)){ // aU(bNc) = (aUb)N(aUc)
                        System.out.println("WRONG... a: " + a + "; b: " + b + "; c: " + c + "; aU(bNc): " + aU_bNc + "; (aUb)N(aUc): " + aUb_N_aUc);
                        ++failures;
                    }
                    if (!aN_bUc.equals(aNb_U_aNc)){ // aN(bUc) = (aNb)U(aNc)
                        System.out.println("WRONG... a: " + a + "; b: " + b + "; c: " + c + "; aN(bUc): " + aN_bUc + "; (aNb)U(aNc): " + aNb_U_aNc);
                        ++failures;
                    }
                    tests += 2;
                }
            }
        }
        System.out.println("ran " + tests + " tests, " + failures + " failed");
        
//        for(IntervalSet<Double> is1: iss){
//            System.out.println(summarize(is1));
//            System.out.println("complement(universe)=" + is1.complement(universe) + "\n\n");
//        }
        
//        for(IntervalSet<Double> is1: iss){
//            for(IntervalSet<Double> is2: iss){
//                System.out.println(summarize(is1, is2));
//            }
//        }
        
        System.out.println("Goodbye World!");
    }
    
}
